On a mission to evacuate the population of the lone planet Sarpedon before its sun Beta Niobi novas, Spock, Kirk and McCoy beam down to investigate why sensors indicate no humanoid life remaining on the planet. They discover a ``library'' staffed by Mr. Atoz (``A to Z'') and his clones which contains history tapes. Kirk offers to evacuate Mr. Atoz, but he tells them to hurry up and pick a destination, and that he himself plans to join his wife and family when the nova comes. It appears that by inserting the record tapes into a machine called the Atavachron, people can be sent back in time. Mr. Atoz confirms Kirk's suspicions that this is indeed what has happened to the inhabitants of the planet.
While viewing a tape, Kirk hears screams and accidentally sends himself to a time period of witch hunts. McCoy and Spock rush after him, but end up transported themselves to 5000 years in the past when the planet was still in an ice age. Meanwhile, Kirk has ``rescued'' a woman from being poked with a sword by challenging her attacker to a swordfight. Only after chasing the man away does Kirk discover that the woman was a thief attempting to rob the gentleman and that furthermore, there is no entrance back to the library. Kirk goes to the wall from which he had emerged and is able to talk to McCoy and Spock, but cannot get to them. When Kirk is arrested by the authorities for aiding a thief, McCoy and Spock ask him what is going on, and the authorities also hear the voices. The woman then betrays Kirk and denounces him as a witch, claiming that he and the ``spirits'' made her steal against her will.
Spock and Bones, on the verge of freezing, are discovered an sheltered by a woman known as Zarabeth. She has been exiled because her kinsman tried to assassinate Zorcon the Tyrant.
Meanwhile, in prison, Kirk is questioned by the Prosecutor. When Kirk mentions the library, the Prosecutor becomes extremely uncomfortable. At first, he tries to maintain that Kirk might indeed be innocent. But when the guard insists that he heard voices talking to Kirk, he is forced to back off. When Kirk then starts repeating the word ``library'' to the Prosecutor, he gets flustered and rushes out saying he wants nothing to do with Kirk. Back in the ice age, Zarabeth tells Spock that the Atavachron alters cell structure and that he therefore cannot return to the future. Meanwhile, Kirk escapes from his cell when he grabs the guard who is trying to pour soup into his bowl and knocks the guard out. When the Prosecutor comes to take Kirk to the inquisition, Kirk realized that he is also sent from the future, and threatens to denounce him as a witch if he does not help Kirk. The Prosecutor then informs Kirk that the Atavachron alters cell structure and brain patterns to prepare people for the past. The Prosecutor has been prepared and cannot return, but Kirk can only survive a few hours and must return. Kirk then finds his way back to the brick wall from which he emerged, and steps back into the library. Mr. Atoz insists that Kirk be prepared, and Kirk is forced to lock one copy of him in a closet and knock out another. The real Mr. Atoz then arrives and zaps Kirk.
Back in the ice age, Spock's personality is slipping to that of the barbaric Vulcans of 5000 years in the past. He falls in love with Zarabeth and believes her when she tells him he cannot go back. McCoy notices the changes in Spock (especially when Spock responds to an insult by grabbing him by the scruff of the neck and announcing ``I don't like that'') and guesses that Zarabeth is not being completely truthful in order to keep Spock with her. Spock also begins to notice that he is not himself when he eats animal flesh and enjoys it. However, this knowledge does not stop him from telling Zarabeth that she is beautiful and then making love to her. While kissing her, he also cracks one of his rare smiles.
Meanwhile, Kirk has managed to recover enough to avoid having Mr. Atoz wheel him into the Atavachron. He overpowers Atoz and forces him to help him locate Spock and McCoy by trying various disks. McCoy has somehow figured out that it is only Zarabeth who cannot return, and confronts Spock with this fact as well as with the fact that he has reverted to the mental state of his barbarian ancestors. Spock manages to drag himself away from Zarabeth and returns with McCoy to the library by following Kirk's voice. With everyone back, Mr. Atoz puts in a disk and rushes to join his family before it is too late. Kirk, Spock, and McCoy return to the Enterprise, which warps out of orbit just as the star novas.